1. Field of the Disclosure
This disclosure relates generally to work stealing, and more particularly to systems and methods for implementing work stealing using a dynamically configurable separation between stealable work items and non-stealable work items.
2. Description of the Related Art
Load balancing when scheduling parallel applications is a difficult task, and work stealing is a widely used technique for addressing it. With this technique, each thread maintains its own local pool of work items, from which it consumes work items and into which it puts new work items that it generates during its execution. When a thread's own local work pool becomes empty, and only then, the thread is allowed to steal work items from the work pools of other threads. This technique has been used in many different contexts, programming languages, and on a wide variety of architectures.
Some common implementations for the thread's local pool are based on the double-ended queue (deque) data structure described by Arora, Blumofe, and Plaxton in 2001 (which is referred to herein as the ABP deque). Various successors and improvements of this algorithm are based on the same principle: the owner of the pool (deque) pushes and pops work items on one side of the deque, and the thieves steal work items from the other side of the deque. With this approach, the operations of the owner rarely conflict with the operations of the thieves, resulting in an efficient implementation for the local operations executed by the owner.